We restate the theoretical statements and the algorithms here for completeness and convenience. Given a normalized monotone submodular function f:2 V! The objective aims to find the partition such that the minimum-valued block in the partition is maximized. For a ground set V and its elements (v1,v2,...,v n) coming in an arbitrary streaming order, the output solution of Alg. 1 has The output solution of Alg. 2 has We construct a set cover function as the tight example for Corollary 1. We illustrate the set cover function graphically in Figure 1. The circles are the areas to cover for the set cover function and the green inner circles and the red triangles are elements in the ground set (the outer yellow circles are not elements). The inner circles (green) largely overlap with the outer circles (yellow).

We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, one formulation of which is $\max_{|A|=k}\min_{i\in\{1,\dots,m\}}f_i(A)$. Krause et al. (2008) showed that when the number of functions $m$ grows as the cardinality $k$ i.e., $m=\Omega(k)$, the problem is inapproximable (unless $P=NP$). For the more general case of matroid constraint, Chekuri et al. (2010) gave a randomized $(1-1/e)-\epsilon$ approximation for constant $m$. The runtime (number of queries to function oracle) scales exponentially as $n^{m/\epsilon^3}$. We give the first polynomial time asymptotically constant factor approximations for $m=o(\frac{k}{\log^3 k})$: $(i)$ A randomized $(1-1/e)$ algorithm based on Chekuri et al. (2010). $(ii)$ A faster and more practical $\tilde{O}(n/\delta^3)$ time, randomized $(1-1/e)^2-\delta$ approximation based on Multiplicative-Weight-Updates. Finally, we characterize the variation in optimal solution value as a function of the cardinality $k$, leading to a derandomized approximation for constant $m$.